Community detectability

There seems to be a fundamental limit of Community structure detection.

References

• Inference and Phase Transitions in the Detection of Modules in Sparse Networks
• Graph Spectra and the Detectability of Community Structure in Networks
• Detectability of communities in heterogeneous networks
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Detectability thresholds and optimal algorithms for community structure in dynamic networks

• Stochastic fluctuations and the detectability limit of network communities

• Algorithm independent bounds on community detection problems and associated transitions in stochastic block model graphs - Stochastic block model